/**
 * N个缓存空间，K个用户，总共M个请求。
 * 第i个用户有Mi个请求。
 * 问如何分配空间，使得缓存不命中数最低。
 * 缓存策略采取未来最久使用。
 * 
 * 首先注意到用户请求是各自独立的，因此可以事先求出User2Gain
 * User2Gain[i][j]表示第i个用户如果分配j个空间，其缓存不命中树是多少
 * 注意到题目求最小值，此处转为最大值似乎更方便一些
 * User2Gain[i][j]实际保存的是 M - 不命中数, 表示第i个用户分配j个空间的收益
 * 预处理最差情况应该是O(Mlog(M))，平均是O(Mlog(M/K))
 * 
 * 令Dij表示前i个用户恰好分配j个空间的最大收益，则
 * 所有的 Di0 = 0
 * Dij = max(D[i - 1][k], 0<=k<=j)
 * 最后答案是 M * K - max(D[K][i])
 * 
 * 注意到直接算是O(N^3)，因此要将边界卡的紧一些。
 * 因为M最大为1000， 所以每个用户平均有 M / K 个请求， 因此每个用户最多分配 M / K 个空间即可
 * 因此第1个用户只需计算到 M / K, 第2个用户计算到 2M/K, ...
 * 所以DP的总循环次数是 (M/K + 2M/K + 3M/K + ... ) * M/K = M^2
 */
#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>
using namespace __gnu_pbds;


using llt = long long;
using Real = double;
using vi = vector<int>;
using pii = pair<int, int>;

__gnu_pbds::priority_queue<pii, function<bool(const pii &, const pii &)>> Q([](const pii & a, const pii & b){
    assert(a.second != b.second);
    return a.second < b.second;
});

int N, K, M;
vector<pii> Req;
vi Lisan;
vector<vi> User2Gain;
vector<vi> D;

int proc(const vi & req, int alloc){
    map<int, pair<vi, int>> req2pos;
    for(int i=0;i<req.size();++i) req2pos[req[i]].first.emplace_back(i);

    Q.clear();
    int k = 1;
    for(auto & p : req2pos){
        p.second.second = 0;
        p.second.first.emplace_back(M + M + k++);
    }

    vi flag(M + 1, 0);
    int ans = 0;
    int used = 0;
    for(int i=0;i<req.size();++i){
        auto r = req[i];
        if(0 == flag[r]){
            ans += 1;

            if(used < alloc){
                used += 1;
            }else{
                while(1){
                    auto h = Q.top();
                    Q.pop();
                    if(h.second > i){
                        flag[h.first] = 0;
                        break;
                    }
                }
            }
        }
        flag[r] = 1;
        auto & mm = req2pos[r];
        Q.push({r, mm.first[++mm.second]});
    }
    return ans;
}

void proc(const vi & req, vi & gain){
    vi flag(M + 1, 0);
    int n = 0;
    for(auto i : req){
        if(flag[i] == 0){
            flag[i] = 1;
            n += 1;
        }
    }
    if(n > N) n = N;
    gain.assign(n + 1, 0);
    gain[0] = M - req.size();
    for(int i=1;i<=n;++i){
        gain[i] = M - proc(req, i);
    }

    return;
}

int proc(){
    Lisan.clear(); Lisan.reserve(M + 1);
    Lisan.emplace_back(0);
    for(const auto & p : Req) Lisan.emplace_back(p.second);
    sort(Lisan.begin(), Lisan.end());
    Lisan.erase(unique(Lisan.begin(), Lisan.end()), Lisan.end());

    vector<vi> user2req(K + 1, vi());
    for(auto & p : Req){
        p.second = lower_bound(Lisan.begin(), Lisan.end(), p.second) - Lisan.begin();
        user2req[p.first].emplace_back(p.second);
    }

    User2Gain.assign(K + 1, vi());
    for(int i=1;i<=K;++i){
        proc(user2req[i], User2Gain[i]);
 
        // cout << i << ":";
        // for(auto j : User2Gain[i]){
        //     cout << " " << M - j;
        // }
        // cout << endl;
    }

    D.assign(K + 1, vi(N + 1, 0));
    int total = 0;
    for(int user=1;user<=K;++user){
        const auto & gain = User2Gain[user];
        total += gain.size() - 1;
        if(total >= N) total = N;
        
        for(int space=0;space<=total;++space){
            int ava = min((int)gain.size() - 1, space);
            auto & tmp = D[user][space];
            
            for(int i=0;i<=ava;++i){
                tmp = max(tmp, D[user-1][space-i] + gain[i]);
            }
        }
        
    }

    int ans = M * K;
    const auto & vec = D[K];
    for(int i=0;i<=N;++i){
        ans = min(ans, M * K - vec[i]);
    }
    return ans;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
    int nofkase = 1;
    cin >> nofkase;
    while(nofkase--){
        cin >> N >> K >> M;
        Req.assign(M, {});
        for(auto & p : Req) cin >> p.first >> p.second;
        cout << proc() << "\n";
    }
    return 0;
}